/*
* dichotomy : 二分 本质对立
*
* 在某一个有序数组中找一个数存不存在
* arr: 1 2 4 5 6 7 7 8
* target: 6
*
*/

function exist(arr, target) {
    if (!arr) return false

    let L = 0,
        R = arr.length - 1,
        mid = 0
    while(L < R) {
        mid = L + ((R - L) >> 1)
        if (arr[mid] === target) {
            return true
        } else if (arr[mid] > target) {
            R = mid - 1
        } else if (arr[mid] < target) {
            L = mid + 1
        }
    }

    return arr[L] === target
}

function test() {
    let arr = Array(10)
    for (let i = 0;i < arr.length;i++) {
        arr[i] = parseInt(Math.random() *10)
    }
    arr.sort((a,b)=>a-b)
    console.log(arr)
    console.log(exist(arr, 4))
}
test()
